# # -*- coding:utf-8
# 5359.
# 最大的团队表现值
# 显示英文描述
# 用户通过次数8
# 用户尝试次数9
# 通过次数8
# 提交次数14
# 题目难度Hard
# 公司有编号为
# 1
# 到
# n
# 的
# n
# 个工程师，给你两个数组
# speed
# 和
# efficiency ，其中
# speed[i]
# 和
# efficiency[i]
# 分别代表第
# i
# 位工程师的速度和效率。请你返回由最多
# k
# 个工程师组成的 ​​​​​​最大团队表现值 ，由于答案可能很大，请你返回结果对
# 10 ^ 9 + 7
# 取余后的结果。
#
# 团队表现值
# 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

mod = 1000000000+7
print(mod)


#超时
from typing import List
import heapq
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        data = [(speed[i],efficiency[i]) for i in range(speed.__len__())]
        mod = 1000000000 + 7
        data.sort(key=lambda x:x[1],reverse=True)
        print(data)
        maxRes = 0
        curSpeLis = []
        for i in range(speed.__len__()):
            curEff = data[i][1]
            curSpeLis.append(data[i][0])
            otherSpeed = []

            otherSpeed = heapq.nlargest(min(k,i+1),curSpeLis)
            print("other:",otherSpeed)
            # otherSpeed.append(data[i][0])
            curRes = curEff*sum(otherSpeed)
            print("cureff,otherspe",curEff,otherSpeed)
            print("curRes",curRes)
            maxRes = max(maxRes,curRes)


        return maxRes%mod

res  = Solution().maxPerformance(3,
[2,8,2],
[2,7,1],
2)
print(res)


from queue import PriorityQueue
class SolutionLeetCode:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        items = [(speed[i], efficiency[i]) for i in range(n)]
        items.sort(key=lambda item:item[1], reverse=True)
        add_sum = 0
        pq = PriorityQueue()
        res = 0
        for i in range(n):
            pq.put(items[i][0])
            add_sum += items[i][0]
            if pq.qsize() > k:
                add_sum -= pq.get()
            val = add_sum * items[i][1]
            if val > res:
                res = val
        return res % (10 ** 9 + 7)


class Solution2:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        comb = [(spd, eff) for spd, eff in zip(speed, efficiency)]
        comb.sort(key=lambda x: x[1], reverse=True)

        sp_list = []
        heapq.heapify(sp_list)
        add_sum = 0
        max_result = 0
        i = 0
        while i < n:
            add_sum += comb[i][0]

            if i > k - 1:
                add_sum -= heapq.heappop(sp_list)
            heapq.heappush(sp_list, comb[i][0])
            val = add_sum * comb[i][1]
            if val > max_result:
                max_result = val
            i += 1

        return max_result % (10 ** 9 + 7)